|
In computer science, Jump Point Search (JPS) is an optimization to the A * search algorithm pathfinding algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning,〔 〕 eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A * considers. Jump point search preserves A *'s optimality, while potentially reducing its running time by an order of magnitude.〔 == History == Harabor and Grastien's original publication provides algorithms for neighbour pruning and identifying successors.〔 The original algorithm for neighbour pruning allowed corner-cutting to occur, which meant the algorithm could only be used for moving agents with zero width; limiting its application to either real-life agents (e.g. robotics) or simulations (e.g. many games). The authors presented modified pruning rules for applications where corner-cutting is not allowed the following year.〔 〕 This paper also presents an algorithm for pre-processing a grid in order to minimise online search times. A number of further optimisations were published by the authors in 2014. These optimizations include exploring columns or rows of nodes instead of individual nodes, pre-computing "jumps" on the grid, and stronger pruning rules. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Jump point search」の詳細全文を読む スポンサード リンク
|